\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 6}}
\end{center}

\noindent{\textbf{Exercise 6.1}}\\\\
a)\\
Let $A_1 = \{w | w $ starts with a zero, followed by any(including zero) number of ones. $\}$.\\
Then $M_1$ recognizes $A_1$.\\\\
Let $A_2 = \{w | w $ is either 1, or 10 $\}$.\\
Then $M_2$ recognizes $A_2$.\\\\
\\
b)\\
The formal definition of M1 is:\\\\
M1 = (Q, $\Sigma$, $\delta$, q$_{0}$, F), where\\
Q= \{q$_{0}$, q$_{1}$, q$_{2}$, q$_{3}$\}\\
$\Sigma$ = \{0,1\}\\
q$_{0}$ $\in$ Q is the start state\\
F = \{q$_{1}$, q$_{2}$\}\\
$\delta$: Q x $\Sigma$ $\rightarrow$ Q defined as follows:\\\\
\begin{tabular}{l|l|l}
  & 0 & 1\\
  \hline
  q$_{0}$ & q$_{1}$ &q$_{3}$ \\ \cline{2-3}
  q$_{1}$ & q$_{3}$ &q$_{2}$ \\ \cline{2-3}
  q$_{2}$ & q$_{3}$ &q$_{2}$ \\ \cline{2-3}
  q$_{3}$ & q$_{3}$ &q$_{3}$ \\
\end{tabular}\\\\\\
\newpage
c)
\begin{center}
\includegraphics[width=0.8\textwidth]{ex6-1c.png}
\end{center}


\vspace{1cm}
\noindent{\textbf{Exercise 6.2}}\\\\
a)\\
We have four states:\\
\begin{enumerate}
\item q1: There is a even number of zeros and ones (note that the empty string is accepted as zero is even)
\item q2: odd \# of ones,  even \#  of zeros
\item q3: even \# of ones,  odd \#  of zeros
\item q4: odd \# of ones,  odd \#  of zeros
\end{enumerate}

\begin{center}
\includegraphics[width=0.8\textwidth]{exercise6_2.pdf}
\end{center}

b)
\begin{center}
\includegraphics[width=0.5\textwidth]{exercise6_2_b.pdf}
\end{center}

\noindent{\textbf{Exercise 6.3}}\\\\
a)\\
 In the following we will prove that is closed under intersection, by construction a DFA that only accepts strings that would be accepted both by $L$ and $L'$, respectively. \\
$M''$ = ($Q''$, $\Sigma''$, $\delta'$, $q''_0$, $F''$).\\
\\
1. $Q''$ = $\{$ ($r_1$, $r_2$) $| r_1$ $\in$ $Q$ and $r_2$ $\in$ $Q'\}$\\
2. assume that $\Sigma'' = \Sigma = \Sigma '$. (otherwise the proof would work as well, but we'd have to introduce error states.)\\
3. we'll use the same transition system as in the proof for the union:\\
For each (r1, r2) $\in$ $Q''$ and each a $\in$ $\Sigma$\\
 $\delta ''((r_1, r_2), a) = (\delta(r_1, a),  \delta '(r_2, a))$\\
4. $q''_0$ is the pair ($q_0$, $q'_0$)\\
5. $F''$ = \{( $r_1$, $r_2$) $|$ $r_1$ $\in$ $F$ and $r_2$ $\in$ $F'$\}\\\\
So only if a state is both a accept state in both of the original languages, it will also be an accept state in the intersection of both.
\\\\
b)\\
 Show that the regular languages are closed under complement, i.e. give a finite automaton
that recognizes \~L.\\\\
Let M1 recognize L  where M1 = (Q1, $\Sigma$, $\delta$, q$_{1}$, F1).\\
We can construct M2 = (Q2, $\Sigma$, $\delta$, q$_{1}$, F2) to recognize \~L in the following way:
\begin{enumerate}
\item Q2 = \{q$_{i}$ $\mid$ q$_{i}$ $\in$ Q1\} (the same states of Q1)
\item $\Sigma$ is the same for M1 and M2
\item $\delta$ is the same for M1 and M2
\item q$_{1}$ initial state is the same for M1 and M2
\item F2 = \{q$_{i}$ $\mid$ q$_{i}$ $\in$ Q1 and q$_{i}$ $\notin$ F1\} (all non accept states of M1 are accept states in M2).
\end{enumerate}
As we can see, the only difference is in the accept states of M2. The accept states of M1 are non accept states in M2 and the non accept states of M1 are accept states in M2. If the initial state of M1 is a non accept state, then M2 also accepts the empty string, which is correct, because it would be part of \~L.
\end{document}

